/**
 * @Author ZhangCuirong
 * @Date 2025/10/11 11:45
 * @description:
 */
public class Solution264 {
    public int nthUglyNumber(int n) {
        int[] ugly = new int[n + 1];
        int p = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        int product2 = 1, product3 = 1, product5 = 1;
        while (p <= n) {
            int min = Math.min(product2, Math.min(product3, product5));
            ugly[p++] = min;
            if (min == product2) {
                product2 = 2 * ugly[p2++];
            }
            if (min == product3) {
                product3 = 3 * ugly[p3++];
            }
            if (min == product5) {
                product5 = 5 * ugly[p5++];
            }
        }
        return ugly[n];

    }

    public static void main(String[] args) {
        Solution264 solution = new Solution264();
        System.out.println(solution.nthUglyNumber(10));
    }
}
